/*
 * Два коня
 * vim:foldmethod=marker:
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>

struct queue {
	int	*data;
	int	head;
	int	size;
	int	size_max;
};

struct Node {
	int x;
	int8_t is_valid;
	int edge_i;
	struct Node *next;
};

struct adjlist {
	struct Node	*first;
	struct Node	*last;
	int8_t	size;

	uint8_t	visited;

	/* Other attributes
	int	color;
	int	conn_sp_id;
	uint8_t	has_bridge; */

	/* bfs */
	int	dist;
	int	prev;
};

static struct chess_map {
	uint8_t		visited, b_busy, w_busy;
	short		b_prev, w_prev;
	int		b_dist, w_dist;
} _map[64 + 1];


/*
 * ranks: rows 1..8
 * files: columns a..h
 */

/* {{{ queue and adjlist interface functions */
void
queue_init(struct queue *q, int size)
{
	q->data = (int *) calloc(size, sizeof *q->data);
	q->head = 0;
	q->size = 0;
	q->size_max = size;
}

void
enqueue(struct queue *q, const int x)
{
	if (q->size >= q->size_max)
		fprintf(stderr, "queue overflow. failed to add x=%d\n", x);
	else
		q->data[(q->head + q->size++) % q->size_max] = x;
}

int
dequeue(struct queue *q)
{
	int ret = q->data[q->head % q->size_max];
	if (!q->size)
		return ret; /* a.k.a. UB */
	--q->size;
	if (++q->head == q->size_max)
		q->head = 0;
	return ret;
}

unsigned char
queue_isempty(const struct queue *q)
{
	return (q->size > 0) ? 0 : 1;
}

void
pushback(struct adjlist *al, int x, int edge_i)
{
	struct Node *newnode;
	newnode = (struct Node *) calloc(1UL, sizeof (struct Node));
	newnode->x        = x;
	newnode->is_valid = 1;
	newnode->edge_i   = edge_i;
	newnode->next     = NULL;
	if (!al->first)
		al->first = newnode;
	else
		al->last->next = newnode;
	al->last = newnode;
	al->size++;
}

void
free_al(struct adjlist *al)
{
	struct Node *n, *p;
	p = n = al->first;
	while (n) {
		n = n->next;
		free(p);
		p = n;
	}
}
/* }}} */

inline int
s_to_int(const char *s)
{
/*
	int rank, file, result;

	file = isupper(s[0]) ? s[0] - 'A' : s[0] - 'a';
	rank = s[1] - '1';
	result = rank * 8 + file;
*/
	return ((s[1] - '1') * 8 + (isupper(s[0]) ? s[0] - 'A' : s[0] - 'a'));
}

void
print_path(const int w_s, const int b_s, const int w_f, const int b_f)
{
}

int
chess_two_knights_s1(struct queue *q, const int w_s, const int b_s, const int w_f, const int b_f)
	/*
	 * Сначала просто находим кратчайшие пути для обоих коней.
	 * Потом, восстанавливая путь проверяем не оказываются ли оба коня в одной клетке.
	 * Если так, то один конь ждёт пока другой освободит клетку (deadlock).
	 */
{
	short int index = start;
	static char w[3];

	_map[index].visited =  1;
	_map[index].prev    = -1;
	_map[index].dist    =  0;
	enqueue(q, index);

	while (!queue_isempty(q)) {
		index = dequeue(q);
#ifdef DEBUG
		w[0] = 'a' + (index % 8);
		w[1] = '1' + (index / 8);
		(void) fprintf(stderr, "index=%*s\n", 2 + _map[index].dist, w);
#endif
		_map[index].visited = 1;
		if (index == final) {
			print_path(index);
			return 0;
		}

		/*
		 * Adding next moves to queue 'q'
		 */
	}

	return -1;
}

int
chess_two_knights_s2()
{
}

int
main(void)
{
	struct queue	q;
	int		b_start, w_start, b_finish, w_finish;
	char		s_b_start[3], s_w_start[3], s_b_finish[3], s_w_finish[3];

	(void) scanf("%s%s%s%s", s_w_start, s_b_start, s_w_finish, s_b_finish);
	queue_init(&q, 9002);
	w_start  = s_to_int(s_w_start);
	b_start  = s_to_int(s_b_start);
	w_finish = s_to_int(s_w_finish);
	b_finish = s_to_int(s_b_finish);

	bfs_chess_two_knights(&q, start, finish);

	free(q.data);
	return 0;
}
